{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 快速排序",
   "id": "bdf1a8563edefb2d"
  },
  {
   "cell_type": "code",
   "id": "initial_id",
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2024-05-06T13:02:14.578009Z",
     "start_time": "2024-05-06T13:02:14.569069Z"
    }
   },
   "source": [
    "def QuickSort(arr: list, p: int, r: int) -> None:\n",
    "    \"\"\"\n",
    "    该快排，当所有元素都相同时不进行递归调用\n",
    "    :param arr: \n",
    "    :param p: \n",
    "    :param r: \n",
    "    :return: \n",
    "    \"\"\"\n",
    "    if p < r:\n",
    "        q, flag = RandomPartition(arr, p, r)\n",
    "        global count\n",
    "        count += 1\n",
    "        if flag:\n",
    "            QuickSort(arr, p, q - 1)\n",
    "            QuickSort(arr, q + 1, r)\n",
    "\n",
    "\n",
    "def RandomPartition(arr: list, p: int, r: int) -> tuple:\n",
    "    i = random.randint(p, r)\n",
    "    arr[r], arr[i] = arr[i], arr[r]\n",
    "    return Partition(arr, p, r)\n",
    "\n",
    "\n",
    "def Partition(arr: list, p: int, r: int) -> tuple:\n",
    "    cur = p\n",
    "    flag = False\n",
    "    for i in range(p, r):\n",
    "        if arr[i] >= arr[r]:\n",
    "            if arr[i] != arr[r]:\n",
    "                flag = True\n",
    "            arr[i], arr[cur] = arr[cur], arr[i]\n",
    "            cur += 1\n",
    "    arr[cur], arr[r] = arr[r], arr[cur]\n",
    "    # return cur\n",
    "    # return cur if flag or cur != r else (p + r) // 2\n",
    "    return cur, flag or cur != r"
   ],
   "outputs": [],
   "execution_count": 207
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-06T13:02:15.774092Z",
     "start_time": "2024-05-06T13:02:15.768259Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "# arr = random.sample(range(100), 100)\n",
    "arr = [0] * 100\n",
    "count = 0\n",
    "print(arr)\n",
    "QuickSort(arr, 0, len(arr) - 1)\n",
    "print(count)\n",
    "print(arr)"
   ],
   "id": "e1cc194bbdd6fb01",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "1\n",
      "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n"
     ]
    }
   ],
   "execution_count": 208
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### Hoare的快排算法",
   "id": "9bd0b4e17c7ed423"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-06T09:25:44.853595Z",
     "start_time": "2024-05-06T09:25:44.845094Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def HoareQuickSort(arr: list, p: int, r: int) -> int:\n",
    "    if p < r:\n",
    "        q = HoarePartition(arr, p, r)\n",
    "        HoareQuickSort(arr, p, q - 1)\n",
    "        HoareQuickSort(arr, q + 1, r)\n",
    "\n",
    "\n",
    "def HoarePartition(arr: list, p: int, r: int) -> int:\n",
    "    x = arr[p]\n",
    "    i = p\n",
    "    j = r\n",
    "    while True:\n",
    "        while i < j and arr[j] < x:\n",
    "            j -= 1\n",
    "        while i < j and arr[i] > x:\n",
    "            i += 1\n",
    "        if i < j:\n",
    "            arr[i], arr[j] = arr[j], arr[i]\n",
    "        else:\n",
    "            return j"
   ],
   "id": "522c55f8ff8f276f",
   "outputs": [],
   "execution_count": 113
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-06T09:25:44.879173Z",
     "start_time": "2024-05-06T09:25:44.872915Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "arr = random.sample(range(100), 100)\n",
    "# arr = [0]*100\n",
    "print(arr)\n",
    "HoareQuickSort(arr, 0, len(arr) - 1)\n",
    "print(count)\n",
    "print(arr)"
   ],
   "id": "7e572eb6439a88db",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 15, 74, 98, 4, 18, 48, 83, 55, 12, 49, 19, 62, 56, 34, 87, 41, 2, 70, 89, 24, 65, 0, 60, 77, 14, 35, 10, 45, 9, 97, 32, 13, 69, 92, 80, 72, 53, 86, 84, 3, 91, 5, 44, 29, 71, 57, 79, 11, 40, 37, 94, 31, 7, 96, 27, 81, 21, 78, 25, 64, 17, 67, 95, 82, 93, 20, 99, 39, 52, 22, 75, 46, 26, 63, 36, 42, 85, 54, 6, 90, 8, 23, 76, 28, 16, 73, 61, 38, 43, 88, 59, 68, 58, 47, 50, 33, 66, 51, 30]\n",
      "66\n",
      "[99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n"
     ]
    }
   ],
   "execution_count": 114
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-06T12:55:04.882671Z",
     "start_time": "2024-05-06T12:55:04.875566Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def ThreePartition(arr: list, p: int, r: int):\n",
    "    \"\"\"\n",
    "    三分快排，当对于要排序的标志位存在复数个的情况下:\n",
    "        存在p<=q<=t<=r\n",
    "        - arr[q...t]中的所有元素相等且等于 flag\n",
    "        - arr[p...q-1]中每个都小于 flag\n",
    "        - arr[t+1...r]中每个都大于 flag\n",
    "    :param arr: 待排序数组\n",
    "    :param p: 左边界\n",
    "    :param r: 有边界\n",
    "    :return: 两个角标，数组在这个范围内的元素都为 flag\n",
    "    \"\"\"\n",
    "    x = arr[r]\n",
    "    i = p\n",
    "    j = p\n",
    "    k = r - 1\n",
    "    num = 1\n",
    "    while i <= k:\n",
    "        if arr[i] > x:\n",
    "            arr[i], arr[j] = arr[j], arr[i]\n",
    "            j += 1\n",
    "            i += 1\n",
    "        elif arr[i] == x:\n",
    "            arr[i], arr[k] = arr[k], arr[i]\n",
    "            k -= 1\n",
    "            num += 1\n",
    "        else:\n",
    "            i += 1\n",
    "    for i in range(num):\n",
    "        arr[j + i], arr[r - i] = arr[r - i], arr[j + i]\n",
    "    return j, j + num - 1\n",
    "\n",
    "\n",
    "def ThreeQuickSort(arr: list, p: int, r: int) -> None:\n",
    "    if p < r:\n",
    "        q, t = ThreePartition(arr, p, r)\n",
    "        ThreeQuickSort(arr, p, q - 1)\n",
    "        ThreeQuickSort(arr, t + 1, r)"
   ],
   "id": "51cea1521a05d272",
   "outputs": [],
   "execution_count": 197
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-06T12:56:53.130541Z",
     "start_time": "2024-05-06T12:56:53.125426Z"
    }
   },
   "cell_type": "code",
   "source": [
    "arr = [random.randint(0, 50) for i in range(100)]\n",
    "# arr = [0]*100\n",
    "# arr = [4, 1, 3, 2, 1, 4, 1, 3, 4, 2]\n",
    "print(arr)\n",
    "# print(ThreePartition(arr, 0, len(arr) - 1))\n",
    "ThreeQuickSort(arr, 0, len(arr) - 1)\n",
    "print(arr)"
   ],
   "id": "d36f3a2ebe04a064",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[50, 34, 3, 22, 6, 47, 36, 2, 15, 26, 49, 12, 35, 46, 3, 4, 29, 7, 44, 24, 27, 13, 26, 29, 6, 50, 13, 5, 47, 23, 29, 8, 5, 38, 36, 39, 24, 29, 23, 2, 43, 11, 48, 49, 27, 18, 16, 29, 18, 18, 15, 16, 41, 46, 20, 27, 30, 20, 11, 40, 10, 12, 2, 35, 41, 31, 50, 24, 18, 3, 35, 5, 42, 0, 39, 15, 25, 44, 49, 43, 24, 10, 7, 47, 14, 13, 16, 32, 44, 43, 34, 20, 39, 37, 32, 32, 49, 8, 41, 28]\n",
      "[50, 50, 50, 49, 49, 49, 49, 48, 47, 47, 47, 46, 46, 44, 44, 44, 43, 43, 43, 42, 41, 41, 41, 40, 39, 39, 39, 38, 37, 36, 36, 35, 35, 35, 34, 34, 32, 32, 32, 31, 30, 29, 29, 29, 29, 29, 28, 27, 27, 27, 26, 26, 25, 24, 24, 24, 24, 23, 23, 22, 20, 20, 20, 18, 18, 18, 18, 16, 16, 16, 15, 15, 15, 14, 13, 13, 13, 12, 12, 11, 11, 10, 10, 8, 8, 7, 7, 6, 6, 5, 5, 5, 4, 3, 3, 3, 2, 2, 2, 0]\n"
     ]
    }
   ],
   "execution_count": 200
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-06T13:08:59.415851Z",
     "start_time": "2024-05-06T13:08:59.411088Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def TailRecursiveQuickSort(arr: list, p: int, r: int) -> None:\n",
    "    \"\"\"\n",
    "    尾递归的快排，若使用随机主元可实现logN的最大栈深度\n",
    "    \"\"\"\n",
    "    while p < r:\n",
    "        q,t = ThreePartition(arr, p, r)\n",
    "        TailRecursiveQuickSort(arr, p, q - 1)\n",
    "        p = t + 1"
   ],
   "id": "cdef41555b46a12e",
   "outputs": [],
   "execution_count": 214
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-06T13:09:06.421465Z",
     "start_time": "2024-05-06T13:09:06.416145Z"
    }
   },
   "cell_type": "code",
   "source": [
    "arr = [random.randint(0, 50) for i in range(100)]\n",
    "# arr = [0]*100\n",
    "# arr = [4, 1, 3, 2, 1, 4, 1, 3, 4, 2]\n",
    "print(arr)\n",
    "# print(ThreePartition(arr, 0, len(arr) - 1))\n",
    "TailRecursiveQuickSort(arr, 0, len(arr) - 1)\n",
    "print(arr)"
   ],
   "id": "b84af862f3802f1f",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 17, 32, 26, 28, 15, 16, 11, 4, 40, 36, 13, 20, 19, 8, 12, 30, 33, 32, 43, 14, 0, 32, 11, 13, 12, 17, 39, 30, 43, 6, 34, 21, 14, 32, 32, 41, 9, 4, 3, 47, 43, 32, 31, 12, 24, 33, 42, 49, 29, 25, 37, 4, 33, 7, 49, 50, 41, 13, 45, 12, 41, 21, 49, 16, 45, 42, 7, 23, 16, 31, 32, 0, 46, 37, 4, 18, 8, 18, 34, 15, 32, 0, 42, 15, 16, 26, 19, 38, 37, 5, 33, 30, 15, 10, 20, 40, 22, 30, 22]\n",
      "[50, 49, 49, 49, 47, 46, 45, 45, 43, 43, 43, 42, 42, 42, 41, 41, 41, 40, 40, 39, 38, 37, 37, 37, 36, 34, 34, 33, 33, 33, 33, 32, 32, 32, 32, 32, 32, 32, 32, 31, 31, 30, 30, 30, 30, 29, 28, 26, 26, 25, 24, 23, 22, 22, 21, 21, 20, 20, 19, 19, 18, 18, 17, 17, 16, 16, 16, 16, 15, 15, 15, 15, 14, 14, 13, 13, 13, 12, 12, 12, 12, 11, 11, 10, 9, 8, 8, 7, 7, 6, 5, 4, 4, 4, 4, 3, 2, 0, 0, 0]\n"
     ]
    }
   ],
   "execution_count": 216
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-08T09:49:56.738604Z",
     "start_time": "2024-05-08T09:49:55.776787Z"
    }
   },
   "cell_type": "code",
   "source": [
    "temp = 0\n",
    "for i in range(10) and temp != 5:\n",
    "    temp = i"
   ],
   "id": "1a0fab6dd6b19b6c",
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'bool' object is not iterable",
     "output_type": "error",
     "traceback": [
      "\u001B[1;31m---------------------------------------------------------------------------\u001B[0m",
      "\u001B[1;31mTypeError\u001B[0m                                 Traceback (most recent call last)",
      "Cell \u001B[1;32mIn[2], line 2\u001B[0m\n\u001B[0;32m      1\u001B[0m temp \u001B[38;5;241m=\u001B[39m \u001B[38;5;241m0\u001B[39m\n\u001B[1;32m----> 2\u001B[0m \u001B[38;5;28;01mfor\u001B[39;00m i \u001B[38;5;129;01min\u001B[39;00m \u001B[38;5;28mrange\u001B[39m(\u001B[38;5;241m10\u001B[39m) \u001B[38;5;129;01mand\u001B[39;00m temp \u001B[38;5;241m!=\u001B[39m \u001B[38;5;241m5\u001B[39m:\n\u001B[0;32m      3\u001B[0m     temp \u001B[38;5;241m=\u001B[39m i\n",
      "\u001B[1;31mTypeError\u001B[0m: 'bool' object is not iterable"
     ]
    }
   ],
   "execution_count": 2
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
